/**
 * Created with IntelliJ IDEA.
 * Description:矩阵最长递增路径
 * User: wangxin
 * Date: 2024-12-26
 * Time: 21:34
 */
public class Test2 {
    private int[][] dirs = new int[][] {{-1,0},{1,0},{0,-1},{0,1}};
    public int dfs(int[][] matrix,int[][]dp,int i,int j){
        int n = matrix.length;
        int m = matrix[0].length;
        if(dp[i][j] != 0){
            return dp[i][j];
        }
        dp[i][j]++;
        for(int k = 0;k < 4;k++){
            int nexti = i + dirs[k][0];
            int nextj = j + dirs[k][1];
            if(nexti >= 0&&nexti < n&&nextj>=0&&nextj < m&&matrix[nexti][nextj] > matrix[i][j])
                dp[i][j] = Math.max(dp[i][j],dfs(matrix,dp,nexti,nextj)+1);
        }
        return dp[i][j];
    }
    public int solve (int[][] matrix) {
        // write code here
        int n = matrix.length;
        int m = matrix[0].length;
        int res = 0;
        int[][] dp = new int[n+1][m+1];
        for(int i = 0;i < n;i++){
            for(int j = 0;j < m;j++){
                res = Math.max( dfs(matrix,dp,i,j),res);
            }
        }
        return res;
    }
}
